import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 123
 * Date: 2023-05-29
 * Time: 20:26
 */
public class BinaryTree {


    static class TreeNode{
        public char val ;
        public TreeNode right ;
       public TreeNode left ;
        public TreeNode(char val){
            this.val = val ;
        }


    }
    public TreeNode createTree(){
          TreeNode A = new TreeNode('A') ;
          TreeNode B = new TreeNode('B') ;
          TreeNode C = new TreeNode('C') ;
          TreeNode D = new TreeNode('D') ;
          TreeNode E = new TreeNode('E') ;
          TreeNode F = new TreeNode('F') ;
          TreeNode G = new TreeNode('G') ;
          TreeNode H = new TreeNode('H') ;
        TreeNode I = new TreeNode('I') ;
          A.left = B ;
          A.right = C ;
          B.left = D ;
          B.right = E ;
          C.left = F ;
          C.right = G ;
          E.left = H ;
          H.right = I ;
          return A ;
    }

public void preOrder(TreeNode root){
        if(root == null){
            return ;
        }
    System.out.print(root.val + "  ");
        preOrder(root.left);
        preOrder(root.right);

}

public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
       inOrder(root.left);
      System.out.print(root.val + "  ");
       inOrder(root.right);


    }

    public void nextOrder(TreeNode root){
        if(root == null){
            return;
        }
        nextOrder(root.left);
        nextOrder(root.right);
        System.out.print(root.val + "  ");

    }

    public List<TreeNode> preOrder2(TreeNode root){
       List<TreeNode> ret = new ArrayList<>();
       if(root == null){
           return ret ;
       }
       ret.add(root) ;
       List<TreeNode> leftList = preOrder2(root.left) ;
       ret.addAll(leftList) ;
        List<TreeNode> rightList = preOrder2(root.right) ;
        ret.addAll(rightList) ;
        return ret ;
    }
    public int nodeSize(TreeNode root){

        if(root == null){
            return 0 ;
        }

        return nodeSize(root.left) + nodeSize(root.right) + 1 ;
    }
    public int leafSize(TreeNode root){
        if(root == null){
            return 0 ;
        }
        if(root.right == null && root.left == null ){
            return 1 ;
        }
        return leafSize(root.left) + leafSize(root.right) ;
    }
    public int getKeySize(TreeNode root ,int key){
        if(root == null){
            return 0 ;
        }
        if(key == 1){
            return 1 ;
        }
        return getKeySize(root.left,key-1) + getKeySize(root.right, key - 1) ;

    }
    public int getTreeHigh(TreeNode root){
        if(root == null){
            return  0 ;
        }
       int leftTreeHigh = getTreeHigh(root.left)  ;
        int rightTreeHigh = getTreeHigh(root.right)  ;
        return leftTreeHigh > rightTreeHigh ? leftTreeHigh + 1: rightTreeHigh + 1;


    }

}
